package main

import (
	"fmt"
	"time"
)

func minDistance(word1 string, word2 string) int {
	m := len(word1)
	n := len(word2)
	f := make([][]int, m+1)
	for i := 0; i <= m; i++ {
		f[i] = make([]int, n+1)
	}
	for i := 0; i <= m; i++ {
		f[i][0] = i
	}
	for j := 0; j <= n; j++ {
		f[0][j] = j
	}
	fmt.Println("初始:", f)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			/*
				f[i+1][j+1] 最终需要走的次数
				word1[i+1] 和 word2[j+1] 不相等的情况下 替换 删除 增加:
					word1[i] 和 word2[j+1] 最小的步骤为 1 公式如下
						f[i+1][j+1] = f[i][j+1] + 1
					word1[i+1] 和 word2[j] 最小的步骤为 1 公式如下
						f[i+1][j+1] = f[i+1][j] + 1
					word1[i] 和 word2[j] 最小的步骤为 1 公式如下
						f[i+1][j+1] = f[i][j] + 1
					因为是计算最优解答 整合的公式:
						f[i+1][j+1] = min(f[i][j+1], f[i+1][j], f[i][j]) +1
				word1[i+1] 和 word2[j+1] 相等的情况下:
					word1[i] 和 word2[j+1] 最小的步骤为 1 公式如下
						f[i+1][j+1] = f[i][j+1] + 1
					word1[i+1] 和 word2[j] 最小的步骤为 1 公式如下
						f[i+1][j+1] = f[i+1][j] + 1
					word1[i+1] 和 word2[j+1] 最小的步骤为 0 公式如下
						f[i+1][j+1] = f[i][j]
					因为是计算最优解答 整合的公式:
						f[i+1][j+1] = min(f[i][j+1], f[i+1][j], f[i][j]-1) +1
			*/

			if word1[i] != word2[j] { // 如果 位置不相等
				f[i+1][j+1] = min(min(f[i][j+1], f[i+1][j]), f[i][j]) + 1
				fmt.Println("不等:", f)
			} else {
				f[i+1][j+1] = min(min(f[i][j+1], f[i+1][j]), f[i][j]-1) + 1
				fmt.Println("相等:", f)
			}
			time.Sleep(time.Second)
		}
		fmt.Println("-------------------")
	}
	return f[m][n]
}

func min(x, y int) int { // 判断大小  返回小的值
	if x < y {
		return x
	} else {
		return y
	}
}

func main() {
	fmt.Println(minDistance("xz", "hsd"))
}
